﻿using System;
using System.Collections.Generic;
using System.Text;
using GraphAPI;
using GraphAPI.Model;
using System.Drawing;

namespace Bridges
{
	public class BridgesAlg : IAlgorithm
	{
		#region IAlgorithm Members

		public string Name
		{
			get { return "Поиск мостов"; }
		}

		public string Description
		{
			get { return "Алгоритм поиска мостов в графе"; }
		}

		public string Category
		{
			get { return ""; }
		}

		public System.Windows.Forms.Control Use(Graph graph)
		{
			bool[,] m = graph.RelationMatrix;
			foreach (Relation rel in graph.Relations)
			{
				int from = graph.GetEntityId(rel.StartEntity);
				int to = graph.GetEntityId(rel.EndEntity);
				m[from, to] = false;
				m[to, from] = false;

				if (!IsWay(m, graph.EntityCount, from, to))
				{
					rel.ColorMark = Color.Aqua;
				}

				m[from, to] = true;
				m[to, from] = true;
			}

			GraphPanel panel = new GraphPanel();
			panel.Graph = graph;

			return panel;
		}

		private bool IsWay(bool[,] m, int size, int from, int to)
		{
			int[] d = new int[size];
			int st = 0;

			for (int i = 0; i < size; i++)
				d[i] = -1;
			d[from] = 0;

			int x = 0;
			do //Делаем шаги
			{
				st++;
				x = 0;

				for (int i = 0; i < size; i++)
				{ //Ищем вершины, из которых будем делать шаг
					if (d[i] == st - 1)
					{	// Смотрим куда можно шагнуть
						for (int j = 0; j < size; j++)
						{
							// Собсно шаг - отмечаем расстояние до вершины
							if (d[j] == -1 && m[i, j])
							{
								if (j == to)
									return true;

								d[j] = st;
								x++;
							}
						}
					}
				}
			}
			while (x > 0);

			return false;
		}

		#endregion
	}
}
